package com.algorithm.liyc.combine;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 0216.组合总和III
 *
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 * 说明：
 * ● 所有数字都是正整数。
 * ● 解集不能包含重复的组合。
 *
 * @author Liyc
 * @date 2024/1/17 16:39
 **/

public class Solution2 {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combineSum(int n, int k) {
        combine1(n, k, 1, 0);
        return result;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     * @param n
     * @param k
     */
    public void combine1(int n, int k, int startIndex, int sum) {
        //剪枝
        if (sum > n) {
            return;
        }
        if (path.size() == k) {
            if (sum == n) {
                result.add(new ArrayList<>(path));
                return;
            }
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            sum += i;
            path.add(i);
            combine1(n, k, i + 1, sum);
            //回溯
            path.removeLast();
            //回溯
            sum -= i;
        }
    }
}
